<?xml version="1.0" encoding="ascii"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
          "DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <title>octant.extern.kdtree.KDTree</title>
  <link rel="stylesheet" href="epydoc.css" type="text/css" />
  <script type="text/javascript" src="epydoc.js"></script>
</head>

<body bgcolor="white" text="black" link="blue" vlink="#204080"
      alink="#204080">
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="octant-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

      <th class="navbar" width="100%"></th>
  </tr>
</table>
<table width="100%" cellpadding="0" cellspacing="0">
  <tr valign="top">
    <td width="100%">
      <span class="breadcrumbs">
        <a href="octant-module.html">Package&nbsp;octant</a> ::
        <a href="octant.extern-module.html">Package&nbsp;extern</a> ::
        <a href="octant.extern.kdtree-module.html">Module&nbsp;kdtree</a> ::
        Class&nbsp;KDTree
      </span>
    </td>
    <td>
      <table cellpadding="0" cellspacing="0">
        <!-- hide/show private -->
      </table>
    </td>
  </tr>
</table>
<!-- ==================== TYPE DESCRIPTION ==================== -->
<h1 class="epydoc">type KDTree</h1><p class="nomargin-top"><span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree">source&nbsp;code</a></span></p>
<pre class="base-tree">
object --+
         |
        <strong class="uidshort">KDTree</strong>
</pre>

<hr />
<p>kd-tree for quick nearest-neighbor lookup</p>
  <p>This class provides an index into a set of k-dimensional points which 
  can be used to rapidly look up the nearest neighbors of any point.</p>
  <p>The algorithm used is described in Maneewongvatana and Mount 1999. The
  general idea is that the kd-tree is a binary trie, each of whose nodes 
  represents an axis-aligned hyperrectangle. Each node specifies an axis 
  and splits the set of points based on whether their coordinate along that
  axis is greater than or less than a particular value.</p>
  <p>During construction, the axis and splitting point are chosen by the 
  &quot;sliding midpoint&quot; rule, which ensures that the cells do not 
  all become long and thin.</p>
  <p>The tree can be queried for the r closest neighbors of any given point
  (optionally returning only those within some maximum distance of the 
  point). It can also be queried, with a substantial gain in efficiency, 
  for the r approximate closest neighbors.</p>
  <p>For large dimensions (20 is already large) do not expect this to run 
  significantly faster than brute force. High-dimensional nearest-neighbor 
  queries are a substantial open problem in computer science.</p>
  <p>The tree also supports all-neighbors queries, both with arrays of 
  points and with other kd-trees. These do use a reasonably efficient 
  algorithm, but the kd-tree is not necessarily the best data structure for
  this sort of calculation.</p>

<!-- ==================== NESTED CLASSES ==================== -->
<a name="section-NestedClasses"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td align="left" colspan="2" class="table-header">
    <span class="table-header">Nested Classes</span></td>
</tr>
<tr>
    <td class="summary" colspan="2">
        <a href="octant.extern.kdtree.KDTree.innernode-class.html" class="summary-name">innernode</a>
    </td>
  </tr>
<tr>
    <td class="summary" colspan="2">
        <a href="octant.extern.kdtree.KDTree.leafnode-class.html" class="summary-name">leafnode</a>
    </td>
  </tr>
<tr>
    <td class="summary" colspan="2">
        <a href="octant.extern.kdtree.KDTree.node-class.html" class="summary-name">node</a>
    </td>
  </tr>
</table>
<!-- ==================== INSTANCE METHODS ==================== -->
<a name="section-InstanceMethods"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td align="left" colspan="2" class="table-header">
    <span class="table-header">Instance Methods</span></td>
</tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="octant.extern.kdtree.KDTree-class.html#__init__" class="summary-sig-name">__init__</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">data</span>,
        <span class="summary-sig-arg">leafsize</span>=<span class="summary-sig-default">10</span>)</span><br />
      Construct a kd-tree.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.__init__">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="octant.extern.kdtree.KDTree-class.html#count_neighbors" class="summary-sig-name">count_neighbors</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">other</span>,
        <span class="summary-sig-arg">r</span>,
        <span class="summary-sig-arg">p</span>=<span class="summary-sig-default">2.0</span>)</span><br />
      Count how many nearby pairs can be formed.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.count_neighbors">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="octant.extern.kdtree.KDTree-class.html#query" class="summary-sig-name">query</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">x</span>,
        <span class="summary-sig-arg">k</span>=<span class="summary-sig-default">1</span>,
        <span class="summary-sig-arg">eps</span>=<span class="summary-sig-default">0</span>,
        <span class="summary-sig-arg">p</span>=<span class="summary-sig-default">2</span>,
        <span class="summary-sig-arg">distance_upper_bound</span>=<span class="summary-sig-default">inf</span>)</span><br />
      query the kd-tree for nearest neighbors</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.query">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="octant.extern.kdtree.KDTree-class.html#query_ball_point" class="summary-sig-name">query_ball_point</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">x</span>,
        <span class="summary-sig-arg">r</span>,
        <span class="summary-sig-arg">p</span>=<span class="summary-sig-default">2.0</span>,
        <span class="summary-sig-arg">eps</span>=<span class="summary-sig-default">0</span>)</span><br />
      Find all points within r of x</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.query_ball_point">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="octant.extern.kdtree.KDTree-class.html#query_ball_tree" class="summary-sig-name">query_ball_tree</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">other</span>,
        <span class="summary-sig-arg">r</span>,
        <span class="summary-sig-arg">p</span>=<span class="summary-sig-default">2.0</span>,
        <span class="summary-sig-arg">eps</span>=<span class="summary-sig-default">0</span>)</span><br />
      Find all pairs of points whose distance is at most r</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.query_ball_tree">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
</table>
<!-- ==================== METHOD DETAILS ==================== -->
<a name="section-MethodDetails"></a>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td align="left" colspan="2" class="table-header">
    <span class="table-header">Method Details</span></td>
</tr>
</table>
<a name="__init__"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">__init__</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">data</span>,
        <span class="sig-arg">leafsize</span>=<span class="sig-default">10</span>)</span>
    <br /><em class="fname">(Constructor)</em>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.__init__">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <pre class="literalblock">
Construct a kd-tree.

Parameters:
===========

data : array-like, shape (n,k)
    The data points to be indexed. This array is not copied, and
    so modifying this data will result in bogus results.
leafsize : positive integer
    The number of points at which the algorithm switches over to
    brute-force.

</pre>
  <dl class="fields">
    <dt>Overrides:
        object.__init__
    </dt>
  </dl>
</td></tr></table>
</div>
<a name="count_neighbors"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">count_neighbors</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">other</span>,
        <span class="sig-arg">r</span>,
        <span class="sig-arg">p</span>=<span class="sig-default">2.0</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.count_neighbors">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <pre class="literalblock">
Count how many nearby pairs can be formed.

Count the number of pairs (x1,x2) can be formed, with x1 drawn
from self and x2 drawn from other, and where distance(x1,x2,p)&lt;=r.
This is the &quot;two-point correlation&quot; described in Gray and Moore 2000,
&quot;N-body problems in statistical learning&quot;, and the code here is based
on their algorithm.

Parameters
==========

other : KDTree

r : float or one-dimensional array of floats
    The radius to produce a count for. Multiple radii are searched with a single
    tree traversal.
p : float, 1&lt;=p&lt;=infinity
    Which Minkowski p-norm to use

Returns
=======

result : integer or one-dimensional array of integers
    The number of pairs. Note that this is internally stored in a numpy int,
    and so may overflow if very large (two billion).

</pre>
  <dl class="fields">
  </dl>
</td></tr></table>
</div>
<a name="query"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">query</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">x</span>,
        <span class="sig-arg">k</span>=<span class="sig-default">1</span>,
        <span class="sig-arg">eps</span>=<span class="sig-default">0</span>,
        <span class="sig-arg">p</span>=<span class="sig-default">2</span>,
        <span class="sig-arg">distance_upper_bound</span>=<span class="sig-default">inf</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.query">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <pre class="literalblock">
query the kd-tree for nearest neighbors

Parameters:
===========

x : array-like, last dimension self.m
    An array of points to query.
k : integer
    The number of nearest neighbors to return.
eps : nonnegative float
    Return approximate nearest neighbors; the kth returned value
    is guaranteed to be no further than (1+eps) times the
    distance to the real kth nearest neighbor.
p : float, 1&lt;=p&lt;=infinity
    Which Minkowski p-norm to use.
    1 is the sum-of-absolute-values &quot;Manhattan&quot; distance
    2 is the usual Euclidean distance
    infinity is the maximum-coordinate-difference distance
distance_upper_bound : nonnegative float
    Return only neighbors within this distance. This is used to prune
    tree searches, so if you are doing a series of nearest-neighbor
    queries, it may help to supply the distance to the nearest neighbor
    of the most recent point.

Returns:
========

d : array of floats
    The distances to the nearest neighbors.
    If x has shape tuple+(self.m,), then d has shape tuple if
    k is one, or tuple+(k,) if k is larger than one.  Missing
    neighbors are indicated with infinite distances.  If k is None,
    then d is an object array of shape tuple, containing lists
    of distances. In either case the hits are sorted by distance
    (nearest first).
i : array of integers
    The locations of the neighbors in self.data. i is the same
    shape as d.

</pre>
  <dl class="fields">
  </dl>
</td></tr></table>
</div>
<a name="query_ball_point"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">query_ball_point</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">x</span>,
        <span class="sig-arg">r</span>,
        <span class="sig-arg">p</span>=<span class="sig-default">2.0</span>,
        <span class="sig-arg">eps</span>=<span class="sig-default">0</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.query_ball_point">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <pre class="literalblock">
Find all points within r of x

Parameters
==========

x : array_like, shape tuple + (self.m,)
    The point or points to search for neighbors of
r : positive float
    The radius of points to return
p : float 1&lt;=p&lt;=infinity
    Which Minkowski p-norm to use
eps : nonnegative float
    Approximate search. Branches of the tree are not explored
    if their nearest points are further than r/(1+eps), and branches
    are added in bulk if their furthest points are nearer than r*(1+eps).

Returns
=======

results : list or array of lists
    If x is a single point, returns a list of the indices of the neighbors
    of x. If x is an array of points, returns an object array of shape tuple
    containing lists of neighbors.


Note: if you have many points whose neighbors you want to find, you may save
substantial amounts of time by putting them in a KDTree and using query_ball_tree.

</pre>
  <dl class="fields">
  </dl>
</td></tr></table>
</div>
<a name="query_ball_tree"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">query_ball_tree</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">other</span>,
        <span class="sig-arg">r</span>,
        <span class="sig-arg">p</span>=<span class="sig-default">2.0</span>,
        <span class="sig-arg">eps</span>=<span class="sig-default">0</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="octant.extern.kdtree-pysrc.html#KDTree.query_ball_tree">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <pre class="literalblock">
Find all pairs of points whose distance is at most r

Parameters
==========

other : KDTree
    The tree containing points to search against
r : positive float
    The maximum distance
p : float 1&lt;=p&lt;=infinity
    Which Minkowski norm to use
eps : nonnegative float
    Approximate search. Branches of the tree are not explored
    if their nearest points are further than r/(1+eps), and branches
    are added in bulk if their furthest points are nearer than r*(1+eps).

Returns
=======

results : list of lists
    For each element self.data[i] of this tree, results[i] is a list of the
    indices of its neighbors in other.data.

</pre>
  <dl class="fields">
  </dl>
</td></tr></table>
</div>
<br />
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="octant-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

      <th class="navbar" width="100%"></th>
  </tr>
</table>
<table border="0" cellpadding="0" cellspacing="0" width="100%%">
  <tr>
    <td align="left" class="footer">
    Generated by Epydoc 3.0.1
    on Mon Apr 20 11:56:30 2009
    </td>
    <td align="right" class="footer">
      <a target="mainFrame" href="http://epydoc.sourceforge.net"
        >http://epydoc.sourceforge.net</a>
    </td>
  </tr>
</table>

<script type="text/javascript">
  <!--
  // Private objects are initially displayed (because if
  // javascript is turned off then we want them to be
  // visible); but by default, we want to hide them.  So hide
  // them unless we have a cookie that says to show them.
  checkCookie();
  // -->
</script>
</body>
</html>
